/**
 * @author zhouyanxiang
 * @create 2020-11-2020/11/14-21:26
 */
public class InsertSort {

    public static void main(String[] args) {
        int[]arr = {10,7,2,4,7,100,3,4,2,1,8,9,19};
        insertSort(arr);
        for(int i = 0; i < arr.length;i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j-1]) {
                arr[j] = arr[j-1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
    }
}
